package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 *
 * @author 覃国强
 * @date 2022-06-07 16:29
 */
public class 题库_0084_柱状图中最大的矩形 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] heights = {2,1,5,6,2,3};
    int area = solution.largestRectangleArea(heights);
    System.out.println(area);
  }

  static
  class Solution {

    /**
     * 使用单调递增栈数据结构
     * 当栈顶需要出栈时即可确定栈顶位置作为高的左边界和右边界
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
      if (heights == null || heights.length == 0) {
        return 0;
      }
      int answer = 0;
      Deque<Integer> incStack = new ArrayDeque<>();
      for (int i = 0; i <= heights.length; ++i) {
        while (!incStack.isEmpty() && (i == heights.length || heights[incStack.peek()] >= heights[i])) {
          int curIndex = incStack.pop();
          int leftIndex = incStack.isEmpty() ? -1 : incStack.peek();
          answer = Math.max(answer, heights[curIndex] * (i - (leftIndex + 1)));
        }
        incStack.push(i);
      }
      return answer;
    }

    /**
     * 本质就是：以每一个柱子为高，找到前一个和后一个比它小的位置
     * @param heights
     * @return
     */
    public int largestRectangleArea1(int[] heights) {
      if (heights == null || heights.length == 0) {
        return 0;
      }
      int answer = 0;
      for (int i = 0; i < heights.length; ++i) {
        if (heights[i] == 0) {
          continue;
        }
        int left = i;
        int right = i;
        while (left >= 0 && heights[left] >= heights[i]) {
          --left;
        }
        while (right < heights.length && heights[right] >= heights[i]) {
          ++right;
        }
        answer = Math.max(answer, heights[i] * (right - (left + 1)));
      }
      return answer;
    }
  }

}
